package main.java.com.itlin.datastructure.btree;

import java.util.Arrays;

public class BTree {

    public static class Node {
        public int[] keys; // 关键字
        public Node[] children; // 孩子
        public int keyNumber; // 有效关键字的个数
        public boolean leaf = true; // 是否为叶子节点
        int t; // 最小度数（孩子数目）

        public Node(int t) { // t >= 2
            this.t = t;
            this.children = new Node[2 * t ];
            this.keys = new int[2 * t - 1];
        }

        public Node(int[] keys) {
            this.keys = keys;
        }

        @Override
        public String toString() {
            return Arrays.toString(Arrays.copyOfRange(keys, 0, keyNumber));
        }

        // 多路查找
        Node get(int key){
            int i = 0;
            while( i < keyNumber){
                if (keys[i] == key){
                    return this;
                }
                if (keys[i] > key){
                    break;
                }
                i++;
            }
            // 执行到此时， keys[i]> key 或 i == keyNumber
            // 如果是叶子节点，直接返回
            if (leaf){
                return null;
            }
            // 不是叶子节点，继续查找
            return children[i].get(key);

        }
        //向指定索引处插入 key
        // [1,3,5]
        // [1,2,3,5]
        void insertKey(int key, int index){
            System.arraycopy(keys, index, keys, index + 1, keyNumber - index);
            keys[index] = key;
            keyNumber++;
        }

        //向指定索引处插入 child
        void insertChild(Node child, int index){
            System.arraycopy(children, index, children, index + 1, keyNumber - index);
            children[index] = child;
        }
        // 删除所需工具方法
        // 移除指定 index 处的 key
        int removeKey(int index){
            int t = keys[index];
            System.arraycopy(keys, index + 1, keys, index, --keyNumber - index);
            return t;

        }
        // 移除最左边的key
        int removeLeftmostKey(){
            return removeKey(0);
        }

        // 移除最右边的key
        int removeRightmostKey(){
            return removeKey(keyNumber - 1);
        }
        // 移除指定 index 处的 child
        Node removeChild(int index){
            Node child = children[index];
            System.arraycopy(children, index + 1, children, index, keyNumber - index);
            //keyNumber--;
            children[keyNumber] = null;
            return child;
        }
        // 移除最左边的child
        Node removeLeftmostChild(){
            return removeChild(0);
        }
        // 移除最右边的child
        Node removeRightmostChild(){
            return removeChild(keyNumber );
        }
        // index 孩子处左边的兄弟
        Node childLeftSibling(int index){
            return index == 0 ? null : children[index - 1];
        }
        // index 孩子处右边的兄弟
        Node childRightSibling(int index){
            return index == keyNumber ? null : children[index + 1];
        }
        // 复制当前节点的所有 key 和 child 到 target
        void moveToTarget(Node target){
            int start = target.keyNumber;
            if (!leaf){
                for (int i = 0; i <= keyNumber; i++){
                    target.children[start + i] = children[i];
                }
            }
            for (int i = 0; i < keyNumber; i++){
                target.keys[target.keyNumber++] = keys[i];
            }
        }
    }

    public Node root;

    int t; // 树中节点的最小度数
    int MIN_KEY_NUMBER; // 最小关键字数
    int MAX_KEY_NUMBER; // 最大关键字数


    public BTree() {
        this(2);
    }

    public BTree(int t) {
        this.t = t;

        root = new Node(t);
        MAX_KEY_NUMBER = 2 * t - 1;
        MIN_KEY_NUMBER = t - 1;
    }

    // 1. 是否存在
    public boolean contains(int key){
        return root.get(key) != null;
    }

    // 2. 新增
    public void put(int key){
        doPut(root, key, null, 0);
    }

    private void doPut(Node node, int key, Node parent, int index){
        int i = 0;
        while(i < node.keyNumber){
            if(node.keys[i] == key){
                return; // 已经存在，走更新的逻辑
            }
            if(node.keys[i] > key){
                break; // 插入的位置 i

            }
            i++;
        }
        //
        if (node.leaf){
            // 插入叶子节点
            node.insertKey(key, i);
            // 节点满了，需要分裂

        }else{
            // 插入的是非叶子节点
            doPut(node.children[i],key,node, i);
            // 节点满了，需要分裂
        }
        if (node.keyNumber == MAX_KEY_NUMBER) {
            split(node, parent, index);
        }

    }

    /**
     * <h3>分裂方法</h3>
     *
     * @param left   要分裂的节点
     * @param parent 分裂节点的父节点
     * @param index  分裂节点是第几个孩子
     */
    public void split(Node left, Node parent, int index){
        // 分裂的是根节点
        if(parent == null){
            // 1. 创建1个新的 根节点
            Node newRoot = new Node(t);
            newRoot.leaf = false;
            newRoot.insertChild(left,0);
            this.root = newRoot;
            parent = newRoot;
        }
        // 1. 创建 right 节点， 把 left 中 t之后的 key 和 child 移动过去
        Node right = new Node(t);
        right.leaf = left.leaf;// 分裂后的节点是叶子节点还是非叶子节点 取决于分裂前的节点属性
        System.arraycopy(left.keys, t, right.keys, 0 , t - 1);
        if (!left.leaf){
            System.arraycopy(left.children, t , right.children, 0 , t);
            for (int i = t; i <= left.keyNumber; i++) {
                left.children[i] = null;
            }
        }
        right.keyNumber = t - 1;
        left.keyNumber = t - 1;
        // 2. 中间的key（t - 1 处）插入到父节点
        int mid = left.keys[t - 1];
        parent.insertKey(mid, index);
        // 3. right 节点作为父节点的孩子
        parent.insertChild(right, index + 1);
    }


    // 3. 删除
    public void remove(int key){
        doRemove(null,root,0,key);

    }

    private void doRemove(Node parent,Node node,int index, int key){
        int i = 0;
        while(i < node.keyNumber){
            if(node.keys[i] >= key){
                break; // 找到要删除的节点
            }
            i++;
        }
        // i: 找到了要删除的节点
        // 没找到： 代表到 第i 个孩子继续查找
        if (node.leaf){
            if(!found(node, key, i)){ //case1: 当前节点是叶子节点，但是没找到要删除的节点
                return;// 找不到，直接返回
            }else{ // case2: 当前节点是叶子节点，找到了要删除的节点
                node.removeKey(i);
            }
        }else {
            if(!found(node, key, i)){ //case3: 当前节点不是叶子节点，但是没找到要删除的节点
                //继续到第i孩子中查找
                doRemove(node,node.children[i],i,key);

            }else{ // case4: 当前节点不是叶子节点，找到了要删除的节点
                // 找到后继节点， 替换当前的值 后， 删除后继节点
                Node s = node.children[i + 1];
                while(!s.leaf){
                    s = s.children[0];
                }
                int sKey = s.keys[0];
                  // 2. 替换待删除的 key
                node.keys[i] = sKey;
                // 3. 删除后继key
                doRemove(node,node.children[i + 1],i + 1,sKey);
            }
        }
        if (node.keyNumber < MIN_KEY_NUMBER) {//case5  case6: 当前节点数量小于最小值，需要调整平衡
            // 节点数量小于最小值，调整平衡
            balance(parent,node,index);
        }



    }

    private void balance(Node parent, Node x, int i){

        //case 6 根节点
        if(x == root){
            if (root.keyNumber == 0 && root.children[0] != null){
                root = root.children[0];
            }
            return;
        }
        Node left = parent.childLeftSibling(i);
        Node right = parent.childRightSibling(i);
        //case 5 -1 左边富裕， 右旋
        if (left != null && left.keyNumber > MIN_KEY_NUMBER){
            //case 5 -1 左边富裕， 右旋
            // 将 索引 i - 1 的 key 旋转下来插入到索引 0 处
            x.insertKey(parent.keys[i - 1],0);
            // 将左边兄弟的孩子给 当前节点
            if (!left.leaf){
                x.insertChild(left.removeRightmostChild(),0);
            }
            // 将左侧富裕的兄弟节点，将其最右边的key 旋转到 父节点 索引 i - 1 处
            parent.keys[i - 1] = left.removeRightmostKey();
            return;
        }
        //case 5 - 2 右边富裕，左旋
        if (right != null && right.keyNumber > MIN_KEY_NUMBER){

            // case5-2右边富裕，左旋
            // a）父节点中后继key旋转下来
            x.insertKey(parent.keys[i],x.keyNumber);
            // b) right中最小的孩子换参
            if(!right.leaf){
                x.insertChild(right.removeLeftmostChild(),x.keyNumber);
            }
            // c）right中最小的key旋转上去
            parent.keys[i] = right.removeLeftmostKey();
            return;
        }

        // case 5 -3 左右都不富裕 ， 向左合并
        if(left != null){
            //向左兄弟合并
            parent.removeChild(i);// 删除当前节点
            left.insertKey(parent.removeKey(i - 1),left.keyNumber);// 删除父节点key，插入到左兄弟
            x.moveToTarget(left);//将待调整节点移动到左兄弟
        }else{
            //向自己合并
            parent.removeChild(i + 1);//删除右侧节点
            x.insertKey(parent.removeKey(i),x.keyNumber);//删除父节点key，插入到待调整节点
            right.moveToTarget(x);//将待调整节点移动到自己
        }

    }

    private static boolean found(Node node, int key, int i) {
        return i < node.keyNumber && node.keys[i] == key;
    }


}
